package sort.simple;

import org.junit.Test;

import java.util.Arrays;

public class BubbleSort {
    @Test
    public void test() {
        int[] a = {5, 2, 7, 4, 1, 3, 8, 9};
        bubbleSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    void bubbleSort(int []nums){
        // 需要进行 nums.length - 1 轮
        for(int i = 0;i < nums.length - 1;i++){
            boolean flag = false;
            for(int j = 0;j < nums.length - 1 - i;j++){
                if(nums[j] < nums[j+1]){
                    swap(nums,j,j+1);
                    flag = true;
                }
            }
            if(!flag){
                return;
            }
        }
    }

    public int[] sortArray(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    flag = true;
                }
            }
            if (!flag) { //如果在一轮冒泡中没有发生任何交换，说明数组已经完成排序了，直接退出
                return nums;
            }
        }
        return nums;
    }

    //    优化最终版 进一步优化比较次数
    public static void bubble_1(int[] a) {
        int n = a.length - 1;
        while (true) {
            int last = 0;
            //记录每一轮冒泡最后一次交换时,前一个元素的位置，它是下一轮冒泡真正要比较的次数
            for (int j = 0; j < n; j++) {
                if (a[j] > a[j + 1]) {
                    swap(j, j + 1, a);
                    last = j;
                }
            }
            n = last;
            if (n == 0) {
                break;
            }
        }
    }

    public static void swap(int i, int j, int[] a) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}